The present invention is generally directed to a system and method for displaying surface information. More particularly, the present invention is directed to a system and method for displaying internal surfaces existing at various depths and locations within a three dimensional body. The images of the surfaces displayed are typically contained within the interior regions of solid bodies which are examined by computed axial tomographic (CAT) x-ray systems or by nuclear magnetic resonance (NMR) imaging systems either of which is capable of generating three-dimensional arrays of data representative of one or more physical properties at various locations within a three-dimensional object. The images generated in the practice of the present invention are particularly useful in that they provide three-dimensional data for examination by physicians, radiologists and other medical practitioners.
In conventional x-ray systems, a two dimensional shadow image is created based upon the different x-ray absorption characteristics of bone and soft tissues. A great improvement on the conventional x-ray system as a diagnostic tool is provided by computed axial tomographic systems, which have been developed over the last ten years or so. These so-called CAT systems are x-ray based and initially were used to produce single two-dimensional views depicting transverse slices of a body, object or patient. Three dimensional information was thereafter gleaned from CAT scan data by generating data for a number of contiguous slices and using the inferential abilities of a radiologist to suggest a three-dimensional representation for the various internal organs. In the present invention, three-dimensional images are generated from the three-dimensional array of data generated by a sequence of such contiguous CAT scans or magnetic resonance imaging scans. The newer magnetic resonance imaging technology possesses the capability to better discriminate between various tissue types, not just between bone and soft tissue and therefore offers the capability for producing more discriminating images in many situations. NMR imaging systems are also capable of generating physiological data rather than just image data. However, whether NMR or CAT systems are employed, data has generally been available only as a sequence of slices, and systems have not generally been available which provide shaded two-dimensional images which accurately depict true three-dimensional views.
A system referred to as "marching cubes" and disclosed in U.S. Pat. No. 4,710,876 has significantly solved some of the major problems associated with the production of high resolution three dimensional medical images. An additional application relating to the display of three-dimensional images and a system referred to as "dividing cubes" was disclosed in U.S. Pat. No. 4,719,535. The contents of these two applications are hereby incorporated herein by reference. Both of these applications are assigned to the same assignee as the present invention. The present invention is in fact applicable to processing an image either in accordance with the marching cubes system or the dividing cubes system or in accordance with other similar systems.
The present invention relates specifically to systems and methods for displaying three dimensional images of various origins. The images may be generated via medical diagnostic techniques, such as computed axial tomography, magnetic resonance, ultrasound, etc. as specifically described in the above noted application. Alternatively, the images may result from solid modeling techniques generated by mechanical design systems, from available topographic information or from various, almost unlimited sources. In all such instances it is desirable to construct a 3-D image and provide a user with the capability of viewing it from different positions and distances and changing such positions interactively as desired. In all such techniques, the data processing required to change the 3-D image to correspond to a selected viewpoint must be done at relatively high speed in order to operate in an interactive mode. Producing a realistic picture of a three-dimensional object on a two-dimensional display presents many problems. How is depth, the third dimension, to be displayed on the screen or display surface? How are parts of objects to be identified and removed from the picture? How are these objects to be rotated, translated, and scaled? There are a number of well known techniques which have been developed to address these questions and which are well known in the art. Several well known techniques for the various aspects of displaying three-dimensional views objects are discussed in "Fundamentals of Interactive Computer Graphics" by J. D. Foley and A. Van Dam.
One particular problem which must be dealt with in order to properly present a new 3-D display in response to changing viewpoint is that of hidden surface elimination or removal. There are several known systems which fit flat polygons to a 3-D surface to within acceptable tolerances and then perform hidden surface removal on the set of polygons. These methods typically employ one of two methods, both of which impair performance.
In a first method, the polygons are sorted by distance from the observer, and drawn on the view surface from back to front. A closer object will overwrite a farther object, thereby obscuring it. This method has the disadvantage that the polygons must be resorted for each new view, which is time-consuming for large images. Furthermore, because the sort operation is sequential, this method cannot easily be implemented using parallel hardware for greater speed.
In a second method the polygons may be drawn on the view surface in any order, but each pixel on the view surface is associated with a depth register or buffer indicating the distance of the surface in the pixel from the viewpoint. As each polygon is drawn, the distance of the polygon at each pixel position is compared to the current value in the pixel distance register; the new information replaces the previous information only if the new distance is less than the previous distance. This technique has the disadvantage that the resolution of the distance register must often be much greater than the resolution of the intensity data for the pixel itself to ensure correct ordering among polygons; 8 bits is generally enough for intensity, while 16-32 bits may be needed for distance. The distance of a polygon from the viewpoint is different at each pixel location in the image, so it must be computed as part of the drawing step. In addition, each distance value must be compared against the previous value before the pixel is updated, which requires an additional pixel memory reference and a comparison operation. The process is exactly equivalent to searching through all the depth or z values that a point (X,Y) can have, assuming that a number of polygons overlap on (X,Y) and assigning to the pixel the appropriate value from the polygon that has the smallest z value. This method is suitable for parallel hardware implementation, but complicated hardware is required for the distance computations, storage and comparisons.
In the above noted patents is disclosed a technique, referred to herein generally as "triangulation", which is used for converting a 3-D grid of density information (an array of volumetric cells or "voxels") into a set of flat polygons (triangles) which approximate the surface contour of a given density value. In implementing the triangulation technique disclosed in the aforementioned applications the surfaces are viewed with commercially available VLSI geometry engines, such as those produced by Weitek, Silicon Graphics, Lexidata, and Ramtek. However, these geometry engines suffer the disadvantages described above with respect to hidden surface removal.
This invention is particularly directed to a method for constructing a geometry engine for the display of triangulated polygons produced by the method disclosed in the aforementioned copending applications which avoids the disadvantages described above. Use of the triangulation method of the copending applications to generate approximating polygons together with the method disclosed herein to display the polygons makes possible implementation of an extremely fast display processor with no bottlenecks.